/** 
 * \file types.h
 *       Filename:  types.h
 * =====================================================================================
 * 
 *    Description:  Definition of OSM data types
 * 
 *        Version:  1.0
 *        Created:  07/11/2009 17:47:33
 *       Revision:  none
 *       Compiler:  gcc
 * 
 *         Author:  François Hissel (fh), francois.hissel@m4x.org
 *        Company:  
 * 
 * =====================================================================================
 */

#ifndef  TYPES_H_INC
#define  TYPES_H_INC

#define	MAX_ATTRIBUTES 40			//!< Maximum number of attributes for an element

/**
 * \struct Field
 * \brief Definition of a field
 *
 * This data type defines a field of attribute, which is represented by its name and an index used to find the associated attribute value in another array.
 */
typedef struct {
	char *name;	//!< Name of the attribute
	unsigned char position;	//!< Position of the attribute in the list of attributes. This field helps to find the associated value of the attribute.
} Field;

/**
 * \struct Description
 * \brief Description of an attribute list
 *
 * This data type is used to describe the attributes of an element. The attributes do not include the identification number, the latitude and longitude which are common data for all geographical elements. Instead, it holds only the attributes specific to one class of elements. Every element type holds a pointer to a Description structure which will be used with another array which actually stores the attributes.
 */
typedef struct {
	Field *names[MAX_ATTRIBUTES];	//!< Array of strings;
	int number;	//!< Number of strings in the list
} Description;

/**
 * \struct Node
 * \brief Data type representing a node, that is a crossroad of the network
 *
 * This data type is used to store a node, which is the memory representation of a crossroad with all its attributes. In particular, it contains the geographic position of the node, as well as different information about it (name, type...). It is designed to allow the definition of any number of attributes. All the attributes are considered as strings, according to the OpenStreetMap format.
 */
typedef struct {
	unsigned long id;	//!< Identification number
	double x;	//!< First coordinate of the crossroad
	double y;	//!< Second coordinate of the crossroad
	Description *description;	//!< Description table of the node
	char *attributes[MAX_ATTRIBUTES];	//!< Array of attributes for this node
	unsigned long number;	//!< Number of times the node appears in a way
} Node;

/**
 * \struct Nodes
 * \brief List of nodes
 *
 * This data type represents a list of an arbitrary number of nodes. It is used in the definition of the Way structure, to hold the member nodes.
 */
typedef struct Nodes {
	Node *node;	//!< Reference to the actual node
	struct Nodes *next;	//!< Next node in the list
} Nodes;

/**
 * \struct Way
 * \brief Data type used to represent a way, which connects several nodes
 *
 * A way connects different nodes and is the memory representation of a road. It may hold its own attributes, in addition to references to the belonging nodes. Like the Node, it is designed to allow the definition of any number of attributes. All the attributes are considered as strings, according to the OpenStreetMap format.
 */
typedef struct {
	unsigned long id;	//!< Identification number
	Nodes *nodes;	//!< List of nodes of the way
	unsigned int nb_nodes;	//!< Number of nodes in the list
	Description *description;	//!< Description table of the way
	char *attributes[MAX_ATTRIBUTES];	//!< Array of attributes for this way
} Way;

/**
 * \struct Ways
 * \brief List of ways
 *
 * This data type represents a list of an arbitrary number of ways.
 */
typedef struct Ways {
	Way *way;	//!< Reference to the actual way
	struct Ways *next;	//!< Next way in the list
} Ways;

/**
 * \brief Look for a field in a description table
 *
 * This function looks for the fiels in the description table given in argument. If a matching element is found, the function returns a pointer to this element. Otherwise, the functions returns a null pointer. The function uses a dichotomy algorithm, so the search has a logarithmic complexity.
 * \param description Description table in which the search will take place
 * \param string Name of the field to search
 * \return If the string is found, pointer to the element in the list. Else, 0.
 */
Field *search(Description *description,char *string);

/**
 * \brief Look for a field in a description table and creates it if it does not exist
 *
 * This function looks for the field with name string in the description table. If it is found, a pointer to the field is returned. Otherwise, a new field is created and inserted in the description table at the right position given the alphabetical order.
 * \param description Description table in which the search will take place
 * \param string Name of the field to search
 * \return Pointer to the field at the end of the function. It can either be an old field with the same name in the list, or a field newly created. 0 if if was not possible to create a new field.
 */
Field *insert_unique(Description *description,char *string);

/**
 * \brief Sort a nodes list by increasing node identifier to allow future fast access
 *
 * This function reads the list of nodes and sorts it using a quick-sort algorithm, which complexity is O(n log n). The list is then converted into an array to allow a fast access to individual elements. The original list, represented by the nodes variable, is destroyed.
 * \param nodes Source list of nodes
 * \param newlist Array in which the new list will be written. This array must not already be initialised. Memory will be allocated to it according to the size of the list of nodes.
 * \return Number of nodes in the list
 */
int sort_nodes(Nodes *nodes,Node ***newlist);

/**
 * \brief Look for a node with given identifier in an array of node.
 *
 * This function searches for a specific node in an array, using a dichotomic algorithm, thus resulting in a logarithmic complexity. If a node is found, a pointer to it is returned. Otherwise, the function returns a null pointer.
 * \param list Array of nodes where the search must take place
 * \param size Number of nodes in the array
 * \param id Identifier of the node to search
 * \return Pointer to the node if it is found, 0 otherwise
 */
Node *find_node(Node **list,int size,unsigned long id);

/**
 * \brief Release the memory occupied by a description table
 *
 * This function frees the memory occupied by a description table. It also destroys all member strings.
 * \param description Description table to free
 */
void free_description(Description *description);

/**
 * \brief Release the memory occupied by a node
 *
 * This function frees the memory occupied by a Node structure. It also destroys all member strings.
 * \param node Node to free
 */
void free_node(Node *node);

/**
 * \brief Release the memory occupied by a way
 *
 * This function frees the memory occupied by a Way structure. It also destroys all member strings and the list of nodes it contains.
 * \param way Way to free
 */
void free_way(Way *way);

/**
 * \brief Release the memory occupied by a Nodes structure
 *
 * This function frees the memory occupied by a Nodes structure, but does not destroy Node within the structure.
 * \param nodes Nodes list which will be freed
 */
void free_nodes(Nodes *nodes);

/**
 * \brief Release the memory occupied by a Ways structure
 *
 * This function frees the memory occupied by a Ways structure, but does not destroy nodes within the structure.
 * \param ways Ways list which will be freed
 */
void free_ways(Ways *ways);


#endif   // ----- #ifndef TYPES_H_INC  -----
